The latest advances in wireless networks have enabled applications such as home and industrial automation, environment monitoring and sensing, security and surveillance; human and goods tracking; and medical monitoring. Typically, such networks are ad hoc, and use very small sensor nodes with a relatively short communications range.
In such wireless network, nodes can only communicate with other nodes that are within transmission range. To communicate with distant nodes requires multi-hop transmissions. Each node has a unique address to facilitate communication among the nodes.
Address allocation and assignment in an ad hoc network is a problem due to the spontaneous nature of the network topology. Nodes can appear and disappear randomly. The geographical distribution of the nodes can be highly irregular. Furthermore, if the nodes are very small sensor nodes, storage, power, transmission range and processing throughput are all limited. This means that addressing schemes used in conventional networks, where the end nodes typically are personal computers, cannot be used.
Typically, the address is assigned to a node when the node ‘joins’ the network in an ad hoc manner. That is, when and where the node joins the network cannot be predicted. The address assignment method should be efficient in terms of storage, power, and processing throughput. The method should be a distributed to avoid bottlenecks and single point of failures. In addition, the distributed addressing method should ensure that no address conflicts occur, i.e., multiple nodes have the same network address, or provide a mechanism for detecting and resolving address conflicts.
The set of addresses is a precious resource in an ad hoc WSN. Therefore, addresses should not be wasted. The addressing method should be error resistant and flexible to adapt to various physical network topologies and geographical distributions of nodes. For example, a dense concentration of nodes in one part of the network should not cause local deficiencies of addresses, even though unused addresses are available in other parts of the network. The distributed addressing method should ideally enable a node to join the network with a high probability when at least one address is unused in the network. Because, the sensor nodes are very small and not perfectly reliable, sensors can be lost. Therefore, the distributed addressing method should be able to identify, reclaim, and reassign the address assigned to nodes that cease to function.
Some addressing schemes, such as the one used by the ZigBee Alliance, use a hierarchical tree of addresses, ZigBee Alliance, “ZigBee Standard Specification in 053474r06ZB_TSC-ZigBee-Specification-v1[1].0”, December 2004. A ZigBee coordinator (ZC) node initially has control over all addresses.
Subsequently, a parent node, beginning with the ZC node, allocates a subset of its set of addresses to a child node when the child node joins network. In the ZigBee scheme, the number of child nodes for any parent node is fixed as a configuration parameter. Therefore, it is possible to systematically determine the subset of the total potential set of addresses that is allocated to a joining child node. That facilitates routing of frames without explicit route discovery via broadcast frames.
However, the static structure of the formats of the ZigBee addresses can waste addresses, or even deny some parent nodes from assigning addresses to potential child nodes. In addition, there is a restriction on the maximum number of levels that the addressing tree can have in the network. Furthermore, a failure of a single node can make nodes with addresses lower in the tree inaccessible. This is a serious problem when the failed node is near the root of the tree.
Another addressing scheme uses a distributed dynamic address assignment protocol, S. Nesargi and R. Prakash, “MANETconf: Configuration of Hosts in a Mobile Ad Hoc Network,” Proceedings of IEEE Infocom, June 2002. That protocol uses a mutual exclusion process, G. Ricart and A. K. Agrawala, “An optimal algorithm for mutual exclusion in computer networks,” Comm. ACM, 24(1), pp. 9-17, 1981. A joining node selects a neighboring node as an initiator node. The initiator node selects an address and broadcasts a frame to notify all other nodes in the network of the selected address. Then, the initiator node waits for responses from the other nodes in the network. If the responses from all of the nodes are positive, meaning no other node is using the selected address, then the initiator node assigns this address to the joining node. Otherwise, the initiator node selects another address.
However, there are several problems with that protocol. All nodes must maintain information about the allocated addresses. This requires memory, which is a limited resource in small sensor nodes. In addition, the broadcast frames and other management frames consume network resources such as bandwidth and power. Moreover, the initiator node can select any address. Therefore, the address assignment does not necessarily follow a regular or systematic pattern. This makes route discovery a problem. Obviously, that addressing scheme is infeasible for ad hoc wireless networks where there can be thousands of sensor nodes.
Another addressing scheme uses a binary partitioning process, M. Mohsin and R. Prakash, “IP Address Assignment in a Mobile Ad Hoc Network,” IEEE Military Communications Conference (MILCOM 2002), volume 2, pp. 856-861, October 2002. Each node maintains a block of available addresses. When a node wants to join the network, the joining node requests an address from a neighboring configuring node. The configuring node partitions the block into two halves, and retains one half of the block, and allocates the other half to the requesting node. Every node maintains an address table to record the blocks of addresses. Each node also broadcasts periodically its block of addresses to enable other nodes to update their address tables. Addresses can also be ‘borrowed’ from other nodes. That scheme also leads to an address assignment that does not follow a regular or systematic pattern. Due to the storage and transmission costs, that addressing scheme is also not suitable for ad hoc wireless sensor networks.
Another scheme performs duplicate address detection, C. E. Perkins, J. T. Malinen, R. Wakikawa, E. M. Belding-Royer, and Y. Sun, “IP Address Autoconfiguration for Ad Hoc Networks,” IETF Internet Draft, draft-ietf-manet-autoconf-01.txt, November 2001. A joining node selects two random addresses, each from a different group of available addresses. One address is used as a temporary source address for a verification process. The other address is intended for final address assignment, pending the verification process. That scheme also requires a large number of broadcast frames, and addresses are generated randomly.
The parent application describes a set of addresses arranged in an N-dimensional hypercube, or generally a parallelepiped, such that each address in the set becomes an n-tuple value. As new nodes join the network, addresses along appropriate dimension can be assigned to these nodes. The assignment of the addresses to the nodes does not deal with address conflict detection and resolution.
The continuation-in-part application of the parent transforms the N-dimensional address set to a tree structure. That transformation enables the addresses to be assigned in a systematic way, such that no address conflicts take place. While that scheme ensures that no address collisions occur, other potentially problematic aspects of tree addressing remain unaddressed.
Specifically, a static tree structure does not adapt well to any geographic topology of the network, e.g., when the nodes the distribution of the nodes is irregular. As a result, a new node may not be able to join in one part of the network due to unavailability of free addresses even though plenty of unused addresses may be available in another remote part of the network. Moreover, that transformation is not efficient in terms of address utilization. More specifically, almost half of the addresses remain unassigned in that scheme, and are effectively discarded. The set of addresses, being a precious resource, should not be underutilized in such a manner.
It should be noted that in most of the above addressing schemes the format of the addresses is fixed. This makes it difficult to adapt the addresses to an ad hoc wireless network where the network topology is constantly changing as nodes join and leave the network.